---
title: "矩阵距离"
created: 2025-11-28
tags:
  - 算法
---

# 矩阵距离

## 题目 [矩阵距离](https://www.acwing.com/problem/content/description/175/)

![[image-7fc253fe.png]]

## 思路分析

题意理解了就好写

给一个由 0 1 组成的矩阵

求矩阵中，各个点到 1 的 最短曼哈顿距离。

如果矩阵中只有 1 个 1，直接从 1 开始进行 bfs，就能求出各个点到 1 这个点的曼哈顿距离。

有多个 1，需将所有的 1 设置为起点进行 bfs

转变成上题差不多的意思 也就是多源 bfs

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=1010;

char g[N][N];

int d[N][N];

int n,m;

int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};

bool isVaild(int x,int y){

	return x>=0 && x<=n-1 && y>=0 && y<=m-1 && d[x][y]==-1;

}

queue<PII> q;

void bfs(){

	while(!q.empty()){

		auto cur=q.front();q.pop();

		int ux=cur.first,uy=cur.second;

		for(int i=0;i<4;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny)){

				d[nx][ny]=d[ux][uy]+1;

				q.push({nx,ny});

			}

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;

	for(int i=0;i<n;i++)

		cin>>g[i];

	memset(d,-1,sizeof d);

	for(int i=0;i<n;i++){

		for(int j=0;j<m;j++){

			if(g[i][j]=='1'){

				q.push({i,j});

				d[i][j]=0;

			}

		}

	}

	bfs();

	for(int i=0;i<n;i++){

		for(int j=0;j<m;j++){

			cout<<d[i][j]<<" ";

		}

		cout<<endl;

	}

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[多源BFS|多源BFS]] 🏠 [[00-刷题理模型]] ➡️ [[血色先锋队|血色先锋队]]